<HTML>

<BODY BGCOLOR="white">

<center>
<FONT SIZE=+2 COLOR="#BB0000">CS346 - Spring 2014<BR>Database System Implementation</FONT>
</center>

<p>
<table border=0 cellpadding=4 cellspacing=10 width="100%">
<tr><td width="100%" bgcolor="#ccccff"><font face="Arial">
<center><b>RedBase Part 5: The Personal Extension</b></center>
<center><b>Proposal Due Wednesday May 14</b></center>
<center><b>Implementation Due Fri. June 6</b></center>
</font></td></tr>
</table>

<ul>
<li> <a href="#intro">Introduction</a>
<li> <a href="#timetable">Timetable</a>
<li> <a href="#scope">Scope and Modifications</a>
<li> <a href="#proposal">The Proposal</a>
<li> <a href="#impl">The Implementation</a>
<li> <a href="#demo">Demo Details and Hints</a>
<li> <a href="#suggestions">Possible Extensions</a>
</ul>

<a name="intro">
<p>
<table border=0 cellpadding=4 cellspacing=10 width="100%">
<tr><td width="100%" bgcolor="#ccccff"><font face="Arial">
<center><b>Introduction</b></center>
</font></td></tr>
</table>

The last part of the RedBase system you will implement is the
<i>Personal Extension</i> (<i>EX</i>).  This part gives you the
opportunity to implement additional features that you've thought about
along the way, more advanced or sophisticated techniques in a part of
the system that interests you the most, or a new system component not
included in the basic RedBase project.

<a name="timetable">
<p>
<table border=0 cellpadding=4 cellspacing=10 width="100%">
<tr><td width="100%" bgcolor="#ccccff"><font face="Arial">
<center><b>Timetable</b></center>
</font></td></tr>
</table>

<p>
<center>
<table border=1>
<tr><th>Date <th>Time <th> Event
<tr><td align="center"> Tuesday May 13 <td align="center"> 1-3 PM <td align="center"> Extra office hours (proposals)
<tr><td align="center"> Wednesday May 14 <td align="center"> 11:59 PM <td align="center"> Proposals due
<tr><td align="center"> Monday May 19 <td align="center">  <td align="center"> Graded proposals posted at <a href="https://www.stanford.edu/class/cs346/cgi-bin/student-center/">Student Center</a>
<tr><td align="center"> Friday June 6 <td align="center"> 2-5 PM <td align="center"> Final project demos
</table>
</center>

<ul>

<li> You must submit a proposal for your personal extension, <a
href="#proposal">described below</a>.  Proposals must be emailed to
<a href="mailto:cs346-staff@cs.stanford.edu">
cs346-staff@cs.stanford.edu</a> by
11:59 PM on Wednesday May 14. Acceptable formats are plain text, pdf
file, postscript file, Word document, or URL for a Web page. No other
formats will be accepted. EX proposals are subject to the same late
policy as project parts.

<p><li> You are encouraged to discuss your ideas and proposal with
the instructor while you are developing them.  In addition to regular
office hours, the TA and/or instructor will
be holding extra office hours.

<!--
<p><li> You will receive written feedback on your proposal, and a
score. Graded proposals will be available for pickup from the course
administrator, Marianne Siroker in Gates 432, starting at 9:00 AM on
Friday May 25.
-->

<p><li> You will discuss and demonstrate the implementation of your
extension during the <a href="#demo">final project demos</a> scheduled
for June 5-6.

<!--
<p><li> You are encouraged to practice your demo with the TA in
advance of the actual graded demo. The TA will be holding extra office
hours Friday June 10 from 4:00-5:30. A computing environment similar
to what you will use during the graded demo will be available.
-->

</ul>

<a name="scope">
<p>
<table border=0 cellpadding=4 cellspacing=10 width="100%">
<tr><td width="100%" bgcolor="#ccccff"><font face="Arial">
<center><b>Scope and Modifications</b></center>
</font></td></tr>
</table>

The personal extension should comprise as a minimum approximately the
same amount of programming effort as, say, the RM component of the
basic project.  One of the motivations behind the formal proposal
process is for us to identify extensions that are likely to be far too
much or too little work (in addition to looking for obvious missing
pieces or design flaws).

<p>Nevertheless, even after proposal feedback, students often make
unanticipated discoveries about their extensions once they are into
the programming process.  The extension may turn out to be much more
or much less work than anticipated, or the overall design may need to
change.  Your proposal should be considered as a guide and not a
contract -- it's no problem to revise your extension along the way, as
long as when demo time arrives you've implemented a complete and
interesting new feature.

<a name="proposal">
<p>
<table border=0 cellpadding=4 cellspacing=10 width="100%">
<tr><td width="100%" bgcolor="#ccccff"><font face="Arial">
<center><b>The Proposal</b></center>
</font></td></tr>
</table>

Your proposal should consist of the following parts:

<ol>

<li> A statement of the general functionality of the proposed
extension.

<p><li> A statement of which components of the basic RedBase system you will
need to modify or extend to accommodate the extension: PF, RM, IX, SM,
QL, and/or the parser.

<p><li> A description and/or diagram of the overall system design of the
extension, including how the extension fits into the rest of RedBase.

<p><li> An interface specification for the most significant C++ classes
and methods you expect to implement for the extension.

<p><li> An informal description of the functionality of each class and
method in the interface.

</ol>

As a guideline, try to make your proposal resemble the
documents/lectures on previous project parts.  Don't forget that the
extension proposal will count toward 5% of your final grade, so it's
worth putting some effort into it.  We'll be looking for a nicely
thought out and well-specified extension of an appropriate scope,
exhibiting an understanding of the RedBase system and of database
system architecture and implementation in general.  Please try to keep
your proposal to approximately 3-5 pages.

<p><i>Although you are welcome to share general ideas with your fellow
students, we ask that proposals be conceived and written up by each
student individually.  For detailed help or feedback please see the
instructor or TA.</i>

<a name="impl">
<p>
<table border=0 cellpadding=4 cellspacing=10 width="100%">
<tr><td width="100%" bgcolor="#ccccff"><font face="Arial">
<center><b>The Implementation</b></center>
</font></td></tr>
</table>

Class names, constants, etc. that are part of your personal extension
should begin with the prefix EX, even when the extension augments an
existing component of the system.  (This convention will allow us to
clearly identify the extension within your code.)  General
implementation principles -- error handling, modularity, documentation,
etc. -- are the same as for the other four project components.
Obviously you will need to develop your own test suite for your
extension.

<p>In considering a particular extension, remember to keep in mind
whether it may require you to modify the PF component or the parser.
Modifying the parser to augment existing commands or add new commands
is not difficult, especially if you have used Yacc in the past.  See
file <tt>Parser.HowTo</tt>, and feel free to obtain help from the TA.
Modifying the PF component also should not be too difficult, as long
as you're willing to plunge into someone else's code.

<a name="demo">
<p>
<table border=0 cellpadding=4 cellspacing=10 width="100%">
<tr><td width="100%" bgcolor="#ccccff"><font face="Arial">
<center><b>Demo Details and Hints</b></center>
</font></td></tr>
</table>

Remember that your project extension and the final demo count for 20%
of your grade in the course.  We suggest before your demo you go over
the following points carefully, and set aside extra time to prepare
for a smooth demo once your coding and debugging are complete.

<ul>

<li> We will stay right on schedule, so please arrive at Gates 433 or 430
a few minutes in advance of the demo time you signed
up for.  Unless other arrangements are made, you will run your demo on
a portable computer, most likely by using <tt>ssh</tt> to one
of the FarmShare machines.

<p><li> Please bring two hard-copies of your <tt>ex_DOC</tt> file to
the demo.  Like previous documentation files, it should describe your
design, key data structures, and testing strategy, and it should be no
more than 2 pages long.  We will also have a copy of your graded demo
proposal on hand.

<p><li> You will meet with the instructors for about 20
minutes.  During the first 5-10 minutes we'll discuss your extension,
its overall design, and perhaps some implementation details.  In the
next 10 minutes or so you'll show us your system.  If there's time
left, you'll sweat while we try out your system with a few queries or
commands of our own.

<p><li> <i>It is to your great benefit to prepare in advance how you
plan to demonstrate your system.</i> You should focus primarily on
your extension, however if you'd also like to exhibit features of
earlier components, you may do so, especially if there are features
you added since you turned in the component.  (For example, if you
were doing poorly early in the course but have worked like mad to
catch up, this is your opportunity to show us.)

<p><li> You don't want to spend all of your time in the demo typing
queries or thinking about what you want to show us, so you definitely
should prepare a script in advance.  Nor should you simply invoke a
large script and let it fly.  Rather, you should plan to use RedBase
in an interactive fashion, cutting and pasting queries or commands
from the script one at a time.  <i>Please practice going through your
script several times in advance of the demo.</i> Also, please don't
show us your exhaustive tests.  Rather, show a representative sample
that concisely demonstrates what your system can do.  How coherently
you demonstrate your system does tend to have an effect on our overall
impression.

<p><li> The TA will be looking over your code for the extension,
although he will not actually run it outside of the demo.  You will
need to submit your code within 30 minutes of your demo ending time.
This is a hard deadline -- the schedule is extremely tight for us to
get all of the grading done, so we must have your code immediately.
Please submit all code that is new for the extension.  Don't bother to
submit libraries or executables, just the <tt>.cc</tt> and <tt>.h</tt>
files.  You will need to hand-create the list of files and save it in
<tt>submit.ex</tt>, then type "<tt>submit -s 5</tt>".

</ul>

<a name="suggestions">
<p>
<table border=0 cellpadding=4 cellspacing=10 width="100%">
<tr><td width="100%" bgcolor="#ccccff"><font face="Arial">
<center><b>Possible Extensions</b></center>
</font></td></tr>
</table>

Here is a list of potential extensions to get you started thinking
about some of the possibilities.  This list is certainly not
exhaustive, and we welcome proposals for extensions not on the list.
The extensions on the list have varying scope, so you may want to
combine smaller extensions or propose a subset of a larger extension.

<ul>

<li> <b>Improved record management:</b> variable-length records,
records spanning page boundaries, records larger than the page size,
records containing structured objects.

<p><li> <b>Binary large objects:</b> "blobs," sometimes called "long
fields," are arbitrarily large, untyped values for attributes (e.g.,
images, postscript files, etc.).  Blobs generally are stored separately
from the data records, are referenced by appropriate pointers, and are
displayed by calling appropriate procedures.

<p><li> <b>Text objects:</b> similar to blobs except objects contain
text, could be text-indexd.

<p><li> <b>Record clustering:</b> attempting to colocate records that
have the same values for one or more attributes.

<p><li> <b>Table partioning:</b> partition tables horizontally or
vertically for more efficient access

<p><li> <b>Storing relations in indexes:</b> storing relations in IX
index files instead of RM record files.

<p><li> <b>Sorted records:</b> maintaining records in sorted order from
the time a relation is created (for a given attribute or set of
attributes), sorting records on demand, using sort order to improve
query execution.

<p><li> <b>Improved indexing:</b> multi-column indexes, additional
indexing methods such as linear hashing, extendible hashing, R-trees,
bitmap indexes.

<p><li> <b>Flexible buffer management:</b> alternate page-replacement
policies, buffer space "chunking"

<p><li> <b>Better join algorithms:</b> nested-block join, sort-merge join,
hash-based join.

<p><li> <b>Join clustering:</b> storing two (or more) relations
together in one file in join order.

<p><li> <b>Additional types of joins:</b> semijoins, outerjoins,
antijoins.

<p><li> <b>Auxiliary structures for joins:</b> join indexes,
pointer-based joins.

<p><li> <b>Query optimization:</b> cost-based selection of query plan
using statistics; statistics maintained on-the-fly or recomputed on
demand.

<p><li> <b>More of SQL:</b> <tt>order-by</tt>, <tt>distinct</tt>,
<tt>group-by</tt> and aggregates, <tt>or</tt>, <tt>not</tt>,
subqueries, <tt>union</tt>, <tt>intersect</tt>, <tt>except</tt>,
<tt>like</tt>.  (Look at a SQL manual and pick features that interest
you.)

<p><li> <b>OLAP support:</b> Star schemas, bitmap indexes and joins

<p><li> <b>XML support:</b> XML storage, XML queries, XML to transmit
requests and/or results

<p><li> <b>Concurrency control:</b> locking, "<tt>begin transaction</tt>"
command, "<tt>commit transaction</tt>" command.

<p><li> <b>Recovery:</b> logging, "<tt>begin transaction</tt>" command,
"<tt>commit transaction</tt>" command, <tt>rollback</tt> command.

<p><li> <b>Security:</b> authentication, authorization management
based on user privileges, encryption.

<p><li> <b>Compression:</b> schemes for reducing storage space for
records, indexes, metadata.

<p><li> <b>Versioning:</b> storing and accessing multiple versions of
each relation or database.

<p><li> <b>Advanced features:</b> external function calls from queries,
stored procedures, views (virtual or materialized), integrity
constraints, triggers, temporal support

<p><li> <b>Networking:</b> client-server model, distributed RedBase,
RedBase as a Web service.

<p><li> <b>Application interface:</b> custom C++ interface or standard
such as ODBC or JDBC.

<p><li> <b>User interface:</b> friendlier and/or more sophisticated
command interface, graphical user interface, HTML or Java-based
interface.

<p><li> <b>System visualization:</b> Query plan visualization and
exploration, query execution visualizer

<pre>


</pre>

</BODY>
